package com.shujujiegou.堆.堆的实现;

import lombok.AllArgsConstructor;
import lombok.Data;

public class Heap {
    private Node[] heapArray;
    private Integer maxSize;
    private Integer currentSize;

    public Heap(int maxSize) {
        this.heapArray = new Node[maxSize];
        this.maxSize = maxSize;
        this.currentSize = 0;
    }

    public boolean insert(int key) {
        Node node = new Node(key);
        if(isEmpty()) {
            heapArray[0] = node;
            this.currentSize ++;
            return true;
        }

        if(isFull()) {
            return false;
        }

        heapArray[currentSize] = node;
        // 向上调整
        this.changeToUp(currentSize ++);
        return true;
    }

    /**
     * 向上调整
     * @param index
     */
    private void changeToUp(int index) {
        int parent =  (index - 1) / 2; // 父亲节点的索引
        Node bottom = this.heapArray[index]; // 将新加的尾节点存入bottom中
        while(index > 0 && bottom.data > this.heapArray[parent].data) {
            this.heapArray[index] = this.heapArray[parent];
            index = parent;
            parent = (parent - 1) / 2;
        }

        heapArray[index] = bottom;
    }

    /**
     * 去掉最大值
     * @return
     */
    public Node remove() {
        if(isEmpty()) {
            return null;
        }

        Node node = heapArray[0];
        this.heapArray[0] = this.heapArray[--currentSize];
        // 向下调整
        this.changeToDown(0);
        // 设置最小的那个数据为空

        this.heapArray[currentSize] = null;

        return node;
    }

    /**
     * 向下调整
     * @param index
     */
    private void changeToDown(int index) {
        Node top = this.heapArray[index];
        int largerIndex;

        // 当前节点存在子节点的时候
        while(index < this.currentSize / 2) {
            int leftIndex = (index * 2) + 1;
            int rightIndex = (index * 2) + 2;
            if(this.heapArray[leftIndex].data < this.heapArray[rightIndex].data) {
                largerIndex = rightIndex;
            } else {
                largerIndex = leftIndex;
            }

            if(top.getData() >= this.heapArray[largerIndex].data) {
                break;
            }

            this.heapArray[index] = this.heapArray[largerIndex];
            index = largerIndex;
        }

        this.heapArray[index] = top;
    }

    public boolean changeValueByIndex(int index, int value) {
        if(index >= this.currentSize || index < 0) {
            return false;
        }

        int oldValue = this.heapArray[index].data;
        this.heapArray[index].data = value;
        if(oldValue < value) {
            // 向上调整
            this.changeToUp(index);
        } else {
            // 向下调整
            this.changeToDown(index);
        }

        return true;
    }

    public void displayHeap() {
        for(int i = 0; i < this.currentSize; ++i) {
            if(null != this.heapArray[i]) {
                System.out.print(this.heapArray[i].data + "》》");
            } else {
                System.out.println("--------end--------");
            }
        }
    }

    public boolean isEmpty() {
        return this.currentSize <= 0  ? true : false;
    }

    public boolean isFull() {
        return this.currentSize == this.maxSize ? true : false;
    }

    @Data
    @AllArgsConstructor
    public class Node{
        private int data;
    }

    public static void main(String[] args) {
        Object[] a = new Object[2];
        a[1] = null;

        Heap heap = new Heap(10);
        heap.insert(1);
        heap.insert(2);
        heap.insert(3);
        heap.insert(4);
        heap.insert(5);
        heap.insert(6);
        heap.insert(7);
        heap.insert(8);
        heap.insert(9);
        heap.insert(10);

        heap.displayHeap();

        System.out.println("");
        System.out.println("<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>");

        heap.remove();
        heap.remove();
        heap.remove();
        heap.displayHeap();

        System.out.println("");
        System.out.println("<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>");
        heap.changeValueByIndex(0, 1);
        heap.displayHeap();
    }
}
